#include <cstdio>
#include <queue>
#include <vector>
#include <memory.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10005;
int n, m;
int d[N];
struct node {
	int v, cost;
};
struct fun {
	int dis, num;
	bool operator < (const fun &x)const {
		return this->dis > x.dis;
	}
};
vector <node> a[N];
priority_queue <fun> q;
bool vis[N];
void Dijstra() {
	while (!q.empty()) {
		int x = q.top().num;
		q.pop();
		if (vis[x]) {
			continue;
		}
		vis[x] = 1;
		for (unsigned i = 0; i < a[x].size(); i++) {
			int v = a[x][i].v, y = a[x][i].cost;
			if (d[v] > d[x] + y) {
				d[v] = d[x] + y;
				q.push ((fun){d[v], v});
			}
		}
	}
}
int main () {
	scanf ("%d%d", &n, &m);
	int x, y, z;
	for (int i = 1; i <= m; i++) {
		scanf ("%d%d%d", &x, &y, &z);
		a[x].push_back((node){y, z});
	}
	fill (d + 1, d + n + 1, 2147483647);
	d[1] = 0;
	q.push((fun){0, 1});
	Dijstra();
	printf ("%d\n", d[n]);
	return 0;
}